The present invention relates in general to array processors and in particular to array processors that are data driven.
Array processors are becoming increasingly desirable for the processing of digital signals, and especially for real-time processing of one-dimensional and multi-dimensional video signals. Appropriate sampling rates for video signals range from about 3 MHz for simple chrominance signals in a TV receiver to 108 MHz and higher for video signals in a high definition television receiver. In high-definition television with flicker-free picture reproduction, it is necessary to interpolate additional interlines from spatially and temporally adjacent picture lines. The spatial reference is defined by the raster-scanned picture plane, and the temporal reference by the picture sequence. A system for real-time processing of these video signals must contain processing elements that can perform these operations simultaneously and that can exchange data in an effective manner. Array processors permit such processing.
An array processor, which consists of a plurality of cells (processing elements) interconnected by data buses, can be classified as either a systolic array processor or a wavefront array processor. The systolic array processor rhythmically computes and passes data in accordance with a global timing-reference "beat." In contrast, the wavefront array processor is data driven. Whenever data is available, a transmitting cell informs a receiving cell to accept the data. A two-way communication scheme (handshaking protocol) between the transmitting and receiving cells ensures that the wavefronts propagate in an orderly manner instead of crashing into one another. Thus, cells in a wavefront array processor must be sequenced instead of timed. One advantage to asynchronous data transfer is that slower cells do not have to hold back faster cells.
Array processors are also classified as single-instruction, multiple-data-stream (SIMD) and multiple-instruction, multiple-data-stream (MIMD). In SIMD array processors, a single processing unit controls the cells. All cells receive the same instruction from the control unit, but operate on different data streams. In MIMD array processors, each cell has its own control unit, program and data. Each cell is individually programmable.
See an article entitled "A programmable video signal processor" by R. J. Sluyter, P. J. et al., in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1989, pages 2476 to 2479. An MIMD array processor adapted for video signal processing has a triangular topology and uses clock-controlled inter-cell communication to process the video signals in real time. Each module consists of five processing elements: three for arithmetic and logic operations and two for memory operations. The elements operate in parallel and are interconnected by a crossbar switch. Each processing element is controlled by a "cyclostatic" program, which is cyclically repeated without break. Thus, there is no branching. All operations are synchronous with a processor clock, whose frequency is a multiple of the sampling frequency.
The architecture of an SIMD wavefront array processor is described in an article entitled "Wavefront Array Processors - Concept to Implementation" by S. Y. Kung, S. C. Co, S. N. Jean and J. N. Hwang in "Computer", Vol. 20, No. 7, July 1987, pages 18 to 33. Each cell communicates with adjacent cells. Asynchronous data transfer between two cells is accomplished by a handshaking protocol in which the data sources and data sinks are buffered by queues, which can be First-In-First-Out (FIFO) memories. For each direction of data flow, one FIFO memory is provided in the data path of two adjacent cells. The handshaking protocol is usually implemented in one clock period.
European Patent Application EP-A O 277 262 discloses an array processor having a plurality of identical cells in a two-dimensional (mesh) array. Thus, each cell can communicate with four adjacent cells via four communication buses. Data transfer is asynchronous from cell to cell. Each cell contains a data memory, an arithmetic logic unit and a shift register.
In an article entitled "The Concept and Implementation of Data-Driven Processor Arrays" by Israel Koren and Irit Peled in Computer, Vol. 20, No. 7, July 1987, on pages 102 to 103 there is described a data-driven MIMD array processor having 50-100 cells that are integrated on a chip using Very Large-Scale Integration (VLSI) technology. The array has a two-dimensional hexagonal structure that allows each cell to exchange data with six adjacent cells via an internal ring-bus system. A cell executes an instruction upon the arrival of all operands required for that instruction. Several global buses within the array processor ensure that each cell can communicate directly with an external host computer.
A one-dimensional systolic MIMD array processor is described in an article entitled "The Warp Computer: Architecture, Implementation, and Performance", by Marco Annaratone et al., in IEEE Transactions on Computers, Vol. C-36, No. 12, December 1987, pages 1523 to 1538. Communication between the individual modules takes place via a queue having a depth of 512 words, sufficient to buffer a scan line of an image. The queue is implemented by a FIFO chip. Flow control for the communication channels is implemented in hardware. When a queue (FIFO) is full or empty, the sender or receiver, respectively, is blocked until the data traffic can be handled by the queue. Thus, when a cell tries to read from an empty queue, it is blocked until a data item arrives. Similarly, when a cell tries to write to a full queue of an adjacent cell, the writing cell is blocked until some data are removed from the full queue. The blocking of the cell is transparent to the program that controls the cell. Two clock generators are required: one for the computational units whose states freeze whenever a cell is blocked, and one for the queues. Latching of data into the queue is controlled by the sender, rather than the receiver. As a cell sends data to an adjacent cell, it also signals the receiving cell's input to accept the data. There is no handshaking between adjacent cells.